package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;
import cn.pugle.oj.catalog.TreeProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 图问题, dfs
 *
 * @author tzp
 * @since 2020/10/19
 */
public class LC207 implements TreeProblem, GraphProblem {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> links = new HashMap<>();
        for (int[] pres : prerequisites) {//{0, 1}, 0的前序是1, 看做 1 -> 0, 1完了之后才能做0
            links.compute(pres[1],
                    (key, oldValue) -> {
                        if (oldValue == null) oldValue = new ArrayList<>();
                        oldValue.add(pres[0]);
                        return oldValue;
                    }
            );
        }
        for (Integer x : new ArrayList<>(links.keySet())) {
            if (!dfs(links, x, new HashSet<>())) return false;
        }
        return true;
    }

    public boolean dfs(Map<Integer, List<Integer>> links, int cur, Set<Integer> path) {
        if (path.contains(cur)) return false;
        if (!links.containsKey(cur)) return true;
        path.add(cur);
        for (Integer pre : links.get(cur)) {
            if (!dfs(links, pre, path)) return false;
        }
        path.remove(cur);
        links.remove(cur);
        return true;
    }

    //numCourses = 2, prerequisites = [[1,0]]
    public static void main(String[] args) {
        System.out.println(new LC207().canFinish(3, new int[][]{{0, 1}, {2, 1}}));
        System.out.println(new LC207().canFinish(3, new int[][]{{0, 1}, {1, 0}}));
    }
}
